Homogénéité du PGCD

Propriété

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) tels que \((a;b) \neq (0;0)\) .

Pour tout \(k \in \mathbb{Z}\) , on a :  \(\mathrm{PGCD}(ka;kb)=\left\vert k \right\vert \times \mathrm{PGCD}(a;b)\) .

Démonstration

Si \(k=0\) , alors l'égalité souhaitée est immédiate (elle donne \(0=0\) ).

Supposons que \(k \neq 0\) .
On reprend l'algorithme d'Euclide pour la division euclidienne de \(a\) par \(b\) , et on multiplie toutes les lignes par \(\left\vert k \right\vert\) . Comme \(\left\vert k \right\vert>0\) , ceci assure que les \(\left\vert k \right\vert r_i\) sont bien les restes dans les divisions euclidiennes successives.

D'après le lemme d'Euclide, on a alors :
\(\begin{align*} \mathrm{PGCD}(\left\vert k \right\vert a;\left\vert k \right\vert b) & =\mathrm{PGCD}(\left\vert k \right\vert b;\left\vert k \right\vert r_1) \\ & =\mathrm{PGCD}(\left\vert k \right\vert r_1;\left\vert k \right\vert r_2) \\ & = \ ... \\ & =\mathrm{PGCD}(\left\vert k \right\vert r_{n-2};\left\vert k \right\vert r_{n-1}) \\& =\mathrm{PGCD}(\left\vert k \right\vert r_{n-1};0) \\ &=\left\vert k \right\vert r_{n-1} \\ &=\left\vert k \right\vert \mathrm{PGCD}(a;b). \end{align*}\)  

Or \(\mathrm{PGCD}(\left\vert k \right\vert a;\left\vert k \right\vert b)=\mathrm{PGCD}(ka;kb)\) , ce qui montre que \(\mathrm{PGCD}(ka;kb)=\left\vert k \right\vert \mathrm{PGCD}(a;b)\) .